package LeetCode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

public class LC_332_ReconstructItinerary {

    public static void main(String[] args) {

    }


    public class Solution {
        HashMap<String, PriorityQueue<String>> map = new HashMap<>();
        LinkedList<String> result = new LinkedList<>();

        public List<String> findItinerary(String[][] tickets) {
            for (String[] ticket : tickets) {
                if (!map.containsKey(ticket[0]))
                    map.put(ticket[0], new PriorityQueue<>());
                map.get(ticket[0]).offer(ticket[1]);
            }
            dfs("JFK");
            return result;
        }

        void dfs(String s) {
            PriorityQueue<String> q = map.get(s);
            while (q != null && !q.isEmpty()) dfs(q.poll());
            result.addFirst(s);
        }

    }
}

